package validparentheses

import (
	"container/list"
	"errors"
)

type Stack struct {
	list.List
}

func (s *Stack) Push(v interface{}) *list.Element {
	return s.PushFront(v)
}

func NewStack() *Stack {
	return &Stack{}
}

func (s *Stack) Pop() (*list.Element, error) {
	if s.Len() == 0 {
		return nil, errors.New("empty stack")
	}
	v := s.Front()
	s.Remove(v)
	return v, nil

}

func isLeftParenthese(c rune) bool {
	switch c {
	case '(':
		return true
	case '[':
		return true
	case '{':
		return true
	default:
		return false
	}
}

func isRightParenthese(c rune) bool {
	switch c {
	case ')':
		return true
	case ']':
		return true
	case '}':
		return true
	default:
		return false
	}
}

func isMatch(a, b rune) bool {
	if (a == '(' && b == ')') || (a == '[' && b == ']') || (a == '{' && b == '}') {
		return true
	}
	return false
}

func isValid(s string) bool {
	stack := NewStack()
	for _, c := range s {
		if isLeftParenthese(c) {
			stack.Push(c)
		}else{
			v, err := stack.Pop()
			if err != nil {
				return false
			}
			d := v.Value.(rune)
			if !isMatch(d, c) {
				return false
			}
		}
	}

	if stack.Len() != 0 {
		return false
	}

	return true

}
